#include <iostream>

int fib(int n)
{
  if (n <= 0) {
    return 0;
  }
  if (1 == n) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

// int fib2_1(int n, int []Memo)
// {
//   if (Memo[n] != -1) {
//     return Memo[n];
//   }
// 
//   if (n <= 2) {
//     Memo[n] = 1;
//   } else {
//     Memo[n] = fib2_1(n - 1, Memo) + fib2_1(n - 2, Memo);
//   }
// 
//   return Memo[n];
// }
// int fib2(int n)
// {
//   if (n <= 0) {
//     return n;
//   }
//   int []Memo = new int[n + 1];
//   for (int i = 0; i <= n; ++i) {
//     Memo[i] = -1;
//   }
//   return fib2_1(n, Memo);
// }

int dynamicFib(int n, int* &memo)
{
  if (n <= 0) {
    return n;
  }

  memo = new int(n + 1);
  if (memo == nullptr) {
    return -1;
  }

  memo[0] = 0;
  memo[1] = 1;
  for (int i = 2; i <= n; ++i) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[n];
}

int main()
{
  return 0;
}

